\documentclass[12pt,a4paper]{article}
\def\pgfsysdriver{pgfsys-dvipdfm.def}

% 加载宏包
\usepackage{fontspec,indentfirst}
\usepackage{xunicode}               % unicode macros
\usepackage{xltxtra}                % fixes/extras
\usepackage[margin=1.5cm] {geometry}
\usepackage{tikz}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage[below]{placeins} % 处理浮动图像
\usepackage{zhspacing}
\zhspacing

% 行间距
\renewcommand{\baselinestretch}{1.2}

% 名词定义
\def\maxforward{最大正向匹配(Maximum Forward Matching)}
\def\maxbackward{最大逆向匹配(Maximum Backward Matching)}
\def\NGram{N-元语法模型(N-Gram Model)}
\def\UniGram{一元语法模型(Unigram Model)}
\def\DijkstraAlgorithm{迪克斯特拉算法(Dijkstra's Algorithm)}

% 标题定义
\title{常用中文分词算法简介}
\author{杨家宁}

% 文章开始
\begin{document}

\maketitle

\def\abstractname{\bf 摘 要}
\begin{abstract}
中文分词的研究时至今日已经产生出了很多种方法。例如：\maxforward 、\maxbackward
还有基于统计语言模型的\NGram 方法。其中\NGram 具有较高的分词准确度，但实现起来
确相对复杂。而\maxforward 方法虽然准确度不高，但由于实现简单因此有比较广泛的应
用。本文将先简单介绍\maxforward 和\maxbackward 算法以及他们的一些问题。再着重介
绍\NGram 中比较简单的一种模型\UniGram 。最后，再介绍一些对模型的修正算法。
\end{abstract}

\section{\maxforward}
\begin{table}
\caption{\maxforward 算法切分句子 “我喜欢奥运会”}
\label{tbl_maxforward}
	\begin{center}
		\begin{tabular}{l|c|l|l}
			当前处理字符串 & 是否匹配    & 目前最长词 & 当前分词结果   \\
			\hline
			我\$           &  Y  & 我         &                \\
			我喜\$         &  N  & 我         &                \\
			我喜欢\$       &  N  & 我         &                \\
			我喜欢奥\$     &  N  & 我         &                \\
			我喜欢奥运\$   &  N  & 我         &                \\
			我喜欢奥运会\$ &  N  & 我         &                \\
			喜\$           &  Y  & 喜         & 我             \\ 
			喜欢\$         &  Y  & 喜欢       & 我             \\ 
			喜欢奥\$       &  N  & 喜欢       & 我             \\ 
			喜欢奥运\$     &  N  & 喜欢       & 我             \\ 
			喜欢奥运会\$   &  N  & 喜欢       & 我             \\ 
			奥\$           &  Y  & 奥         & 我 喜欢        \\ 
			奥运\$         &  Y  & 奥运       & 我 喜欢        \\ 
			奥运会\$       &  Y  & 奥运会     & 我 喜欢        \\ 
		    \$             &          &            & 我 喜欢 奥运会 \\
		\end{tabular}
	\end{center}
\end{table}

我们先来讲解\maxforward 算法。所谓“最大正向”，顾名思义就是从句子开头向结尾搜
索，使得每次切分出来的词的长度最大。表\ref{tbl_maxforward}一步步演示了
\maxforward 的切分过程。详细的算法描述，见算法\ref{alg_maxforward}。

\begin{algorithm}
	\label{alg_maxforward}
	\dontprintsemicolon
	\linesnumbered
	\SetKwData{Token}{token}
	\SetKwData{MaxTokenSize}{max}
	\SetKwData{Result}{result}
	\SetKwFunction{Strlen}{strlen}
	\SetKwFunction{Substr}{substr}
	\SetKwFunction{Concat}{concat}
	\SetKwFunction{Find}{find}
	\SetKwInOut{Input}{Input}
	\SetKwInOut{Output}{Output}

	\Input{A string in chinese $s$}
	\Output{A string after Segmentation $t$}
	\Begin{
		\For{$i\leftarrow 0$ \KwTo \Strlen{$s$}}{
			\For{$j\leftarrow$ \MaxTokenSize \KwTo $0$} {
				\Token$\leftarrow$\Substr{$s$, $i$, $j$}\;
				\If{\Find{\Token}} {
					break\;
				}
			}
			\Concat{$t$, \Token}\;
			\Concat{$t$, $" "$}\;
			$i\leftarrow i + j - 1$\;
		}
	}
	\caption{\maxforward}
\end{algorithm}

\maxforward 虽然简单，但很多时候会因为切词过长导致错误。
例如，句子“研究生命起源”，会被\maxforward 切分成 “研究生 命 起源”。显然是错误的。

\section{\maxbackward}

现在让我们把\maxforward 方法反过来，也就是从后向前反向扫描句子。\ref{tbl_maxbackward}向我们展示了这个过程。

\begin{table}
\caption{\maxbackward 算法切分句子 “研究生命起源”}
\label{tbl_maxbackward}
	\begin{center}
		\begin{tabular}{l|c|l|l}
			当前处理字符串           & 是否匹配 & 目前最长词 & 当前分词结果   \\
			\hline
			源\$                     &  Y  & 源         &                \\
			起源\$                   &  Y  & 起源       &                \\
			命起源\$                 &  N  & 起源       &                \\
			生命起源\$               &  N  & 起源       &                \\
			研究生命起源\$           &  N  & 起源       &                \\

			命\$                     &  Y  & 命         & 起源           \\
			生命\$                   &  Y  & 生命       & 起源           \\
			究生命\$                 &  N  & 生命       & 起源           \\
			研究生命\$               &  N  & 生命       & 起源           \\

			究\$                     &  Y  & 究         & 生命 起源      \\
			研究\$                   &  Y  & 研究       & 生命 起源      \\

			\$                       &          &            & 研究 生命 起源 \\
		\end{tabular}
	\end{center}
\end{table}

这种把\maxforward 扫描方向倒转过来的方法被称为\maxbackward 虽然\maxbackward 把
上面这句\maxforward 切分错误的句子正确切分，但是我们不难发现单纯翻转扫描方式还
是不能解决切词过长的问题，例如：“欢迎来北京”，会被\maxbackward 切分成“欢 迎来 北京”。

虽然\maxforward 和\maxbackward 存在都切分过长导致错误的问题，但在实践中
\maxbackward 的准确率略高于\maxforward

\section{\UniGram}

下面我们来介绍一种稍微复杂一点的算法\UniGram，他有比\maxforward 和\maxbackward
高得多的准确率。

\UniGram 是\NGram 的一种，也是其中最简单的一种。\UniGram 算法力图找到一种切分，
让被切分后的句子中所有词的概率总和最大。下面我们介绍一种称作\DijkstraAlgorithm
的算法来高效地解决这个问题。\footnote{直接而草率的思维会指导我们枚举所有的切分
可能，然后逐个计算每种切分里所有词的概率总和。但是只要稍加计算我们就会发现，一
个含有32个字的句子大约会产生约20亿种切分。即使对于计算机说来遍历这些切分也需要
很大的代价。}

%首先，我们把一句话想像成一张网。构成这张网的办法如下：以从第一个字开始到句子结尾
%每一种长度的子串作为一个新的点与起点$S$相连接。接下来把每一个点所代表的字串的最
%后一个字开始直到句子结尾的每一种长度的子串再作为一个新的点与产生这个点的点相连。
%直到句子结束。把最后产生的点与终点$E$相连接。最后我们把每一条边标记上这个边起点
%所代表单词的概率，以S为起点的边标记为0。

\begin{algorithm}
	\label{alg_maxforward}
	\dontprintsemicolon
	\linesnumbered
	\SetKwData{Token}{token}
	\SetKwData{MaxTokenSize}{max}
	\SetKwData{Result}{result}
	\SetKwData{BackRef}{backref}
	\SetKwData{Score}{score}
	\SetKwData{Prob}{prob}
	\SetKwFunction{Strlen}{strlen}
	\SetKwFunction{Substr}{substr}
	\SetKwFunction{Concat}{concat}
	\SetKwFunction{GetProb}{probability}
	\SetKwInOut{Input}{Input}
	\SetKwInOut{Output}{Output}

	\Input{A string in chinese $s$}
	\Output{A string after Segmentation $t$}
	\Begin{
		\Score $\leftarrow [0, 0, 0, ...]$ \;
		\BackRef $\leftarrow [0, 0, 0, ...]$ \;
		\For{$i\leftarrow 0$ \KwTo \Strlen{$s$}}{
			\For{$j\leftarrow$ $0$ \KwTo \MaxTokenSize} {
				\Token $\leftarrow$ \Substr{$s$, $i$, $j$}\;
				\Prob $\leftarrow$ \GetProb{\Token}\;
				\If {\Score$[ i + j ]$  $<$ \Score$[ i ]$ $ + $ \Prob } {
					\Score$[ i + j ]$ $\leftarrow$ \Score$[i]$ + \Prob \;
					\BackRef$[i]$ $\leftarrow i$;
				}
			}
		}
		\While{$i > 0$} {
			\Token$\leftarrow$\Substr{$s$, \BackRef$[i]$, $i - $ \BackRef$[i]$}\;
			\Concat{$t$, \Token}\;
			\Concat{$t$, $" "$}\;
			$i \leftarrow$ \BackRef$[i]$
		}
	}
	\caption{\maxforward}
\end{algorithm}




\end{document}
